package com.javaDemo.ti;

import java.util.*;

/**
 * 算法题目集合类
 * 包含回溯算法、贪心算法等经典问题的详细解析和测试用例
 * 
 * @author csy
 * @description 面试中常见算法题目的详细解析与测试
 */
public class CursorCreate {

    // =============== 回溯算法部分 ===============

    /**
     * 【组合问题】组合总和 (LeetCode 39)
     * 
     * 题目描述：
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
     * 找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。
     * 你可以按 任意顺序 返回这些组合。
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     * 
     * 示例：
     * 输入：candidates = [2,3,6,7], target = 7
     * 输出：[[2,2,3],[7]]
     * 解释：
     * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
     * 7 也是一个候选， 7 = 7 。
     * 仅有这两种组合。
     * 
     * 提示：
     * 1 <= candidates.length <= 30
     * 2 <= candidates[i] <= 40
     * candidates 的所有元素 互不相同
     * 1 <= target <= 40
     * 
     * 解题思路详解：
     * 1. 为什么用回溯？
     * - 需要找到所有可能的组合（穷举性）
     * - 每个数字可以重复使用，形成多层决策树
     * - 需要考虑所有可能的组合方式
     * 
     * 2. 回溯三要素：
     * a) 选择列表：candidates数组中的所有数字
     * b) 路径：当前已经选择的数字序列
     * c) 结束条件：
     * - 当前和等于target（收集结果）
     * - 当前和超过target（剪枝）
     * 
     * 3. 优化策略：
     * - 排序数组以便提前剪枝
     * - 使用start参数避免重复组合
     * - 当和超过target时立即返回
     * 
     * 4. 复杂度分析：
     * - 时间复杂度：O(N^(T/M))，其中N是数组长度，T是目标值，M是数组中的最小值
     * - 空间复杂度：O(T/M)，递归调用栈的深度
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0)
            return results;

        Arrays.sort(candidates); // 排序用于剪枝
        backtrackCombination(candidates, target, 0, new ArrayList<>(), 0, results);
        return results;
    }

    private void backtrackCombination(int[] candidates, int target, int sum,
            List<Integer> current, int start, List<List<Integer>> results) {
        if (sum == target) {
            results.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (sum + candidates[i] > target)
                break; // 剪枝

            current.add(candidates[i]);
            backtrackCombination(candidates, target, sum + candidates[i], current, i, results);
            current.remove(current.size() - 1); // 回溯
        }
    }

    /**
     * 【排列问题】全排列 (LeetCode 46)
     * 
     * 题目描述：
     * 给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。
     * 你可以 按任意顺序 返回答案。
     * 
     * 示例：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     * 
     * 提示：
     * 1 <= nums.length <= 6
     * -10 <= nums[i] <= 10
     * nums 中的所有整数 互不相同
     * 
     * 解题思路详解：
     * 1. 为什么用回溯？
     * - 需要穷举所有可能的排列顺序
     * - 每个位置都需要尝试所有未使用的数字
     * 
     * 2. 回溯三要素：
     * a) 选择列表：所有未被使用的数字
     * b) 路径：当前已经选择的数字序列
     * c) 结束条件：路径长度等于数组长度
     * 
     * 3. 实现要点：
     * - 使用visited数组标记已使用的数字
     * - 需要考虑每个位置放置每个数字的可能性
     * - 回溯时恢复现场
     * 
     * 4. 复杂度分析：
     * - 时间复杂度：O(N!)，其中N是数组长度
     * - 空间复杂度：O(N)，递归调用栈的深度
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return results;

        boolean[] visited = new boolean[nums.length];
        backtrackPermute(nums, visited, new ArrayList<>(), results);
        return results;
    }

    private void backtrackPermute(int[] nums, boolean[] visited,
            List<Integer> current, List<List<Integer>> results) {
        if (current.size() == nums.length) {
            results.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i])
                continue;

            visited[i] = true;
            current.add(nums[i]);
            backtrackPermute(nums, visited, current, results);
            current.remove(current.size() - 1);
            visited[i] = false;
        }
    }

    // =============== 贪心算法部分 ===============

    /**
     * 【区间问题】会议室安排 (类似于 LeetCode 252)
     * 
     * 题目描述：
     * 给定一个会议时间安排的数组 intervals，其中 intervals[i] = [start, end] ，
     * 表示会议 i 开始于 start，结束于 end 。
     * 请你计算最多能安排多少个会议。每个会议都必须完整进行，不能有任何重叠。
     * 
     * 示例：
     * 输入：intervals = [[0,30],[5,10],[15,20]]
     * 输出：2
     * 解释：可以安排 [5,10] 和 [15,20] 这两个会议
     * 
     * 提示：
     * 1 <= intervals.length <= 10^4
     * 0 <= start < end <= 10^6
     * 
     * 解题思路详解：
     * 1. 为什么用贪心？
     * - 局部最优：优先安排结束时间早的会议
     * - 全局最优：能安排的会议数量最多
     * 
     * 2. 贪心策略证明：
     * - 假设最优解不包含结束最早的会议A
     * - 那么必然包含一个与A时间重叠的会议B
     * - 用A替换B，得到的方案不会比原方案差
     * - 因此，选择结束最早的会议一定是最优的
     * 
     * 3. 复杂度分析：
     * - 时间复杂度：O(NlogN)，主要是排序的时间
     * - 空间复杂度：O(1)，只需要常数空间
     */
    public int maxMeetings(int[][] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;

        // 按结束时间排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int count = 1;
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }

        return count;
    }

    /**
     * 【跳跃问题】跳跃游戏 (LeetCode 55)
     * 
     * 题目描述：
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标。
     * 
     * 示例：
     * 输入：nums = [2,3,1,1,4]
     * 输出：true
     * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
     * 
     * 提示：
     * 1 <= nums.length <= 10^4
     * 0 <= nums[i] <= 10^5
     * 
     * 解题思路详解：
     * 1. 为什么用贪心？
     * - 局部最优：每次都尽可能到达最远位置
     * - 全局最优：最终能够到达最后一个位置
     * 
     * 2. 贪心策略证明：
     * - 如果能到达某个位置，那么一定能到达它前面的所有位置
     * - 因此只需要关注能到达的最远位置
     * 
     * 3. 复杂度分析：
     * - 时间复杂度：O(N)，其中N是数组长度
     * - 空间复杂度：O(1)，只需要常数空间
     */
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0)
            return false;

        int maxReach = 0;

        for (int i = 0; i <= maxReach && i < nums.length; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1)
                return true;
        }

        return false;
    }

    // =============== 测试方法部分 ===============

    /**
     * 组合总和测试方法
     */
    public void testCombinationSum() {
        System.out.println("\n=== 组合总和测试 ===");

        // 测试用例1：标准情况
        int[] candidates1 = { 2, 3, 6, 7 };
        int target1 = 7;
        System.out.println("测试1 - 标准情况：");
        System.out.println("输入数组：" + Arrays.toString(candidates1));
        System.out.println("目标和：" + target1);
        System.out.println("所有组合：" + combinationSum(candidates1, target1));

        // 测试用例2：无解情况
        int[] candidates2 = { 2, 4, 6, 8 };
        int target2 = 3;
        System.out.println("\n测试2 - 无解情况：");
        System.out.println("输入数组：" + Arrays.toString(candidates2));
        System.out.println("目标和：" + target2);
        System.out.println("所有组合：" + combinationSum(candidates2, target2));

        // 测试用例3：单个数字重复使用
        int[] candidates3 = { 2 };
        int target3 = 6;
        System.out.println("\n测试3 - 单个数字重复使用：");
        System.out.println("输入数组：" + Arrays.toString(candidates3));
        System.out.println("目标和：" + target3);
        System.out.println("所有组合：" + combinationSum(candidates3, target3));

        // 测试用例4：多种组合可能
        int[] candidates4 = { 2, 3, 5 };
        int target4 = 8;
        System.out.println("\n测试4 - 多种组合可能：");
        System.out.println("输入数组：" + Arrays.toString(candidates4));
        System.out.println("目标和：" + target4);
        System.out.println("所有组合：" + combinationSum(candidates4, target4));
    }

    /**
     * 全排列测试方法
     */
    public void testPermute() {
        System.out.println("\n=== 全排列测试 ===");

        // 测试用例1：标准情况
        int[] nums1 = { 1, 2, 3 };
        System.out.println("测试1 - 标准情况：");
        System.out.println("输入数组：" + Arrays.toString(nums1));
        System.out.println("所有排列：" + permute(nums1));

        // 测试用例2：单个元素
        int[] nums2 = { 1 };
        System.out.println("\n测试2 - 单个元素：");
        System.out.println("输入数组：" + Arrays.toString(nums2));
        System.out.println("所有排列：" + permute(nums2));

        // 测试用例3：两个元素
        int[] nums3 = { 1, 2 };
        System.out.println("\n测试3 - 两个元素：");
        System.out.println("输入数组：" + Arrays.toString(nums3));
        System.out.println("所有排列：" + permute(nums3));

        // 测试用例4：包含负数
        int[] nums4 = { -1, 0, 1 };
        System.out.println("\n测试4 - 包含负数：");
        System.out.println("输入数组：" + Arrays.toString(nums4));
        System.out.println("所有排列：" + permute(nums4));
    }

    /**
     * 会议室安排测试方法
     */
    public void testMaxMeetings() {
        System.out.println("\n=== 会议室安排测试 ===");

        // 测试用例1：标准情况
        int[][] intervals1 = { { 1, 4 }, { 2, 5 }, { 3, 6 }, { 4, 7 }, { 5, 8 }, { 6, 9 } };
        System.out.println("测试1 - 标准情况：");
        System.out.println("会议时间安排：" + Arrays.deepToString(intervals1));
        System.out.println("最多可以安排的会议数：" + maxMeetings(intervals1));

        // 测试用例2：重叠会议
        int[][] intervals2 = { { 1, 4 }, { 2, 3 }, { 3, 4 }, { 1, 2 } };
        System.out.println("\n测试2 - 重叠会议：");
        System.out.println("会议时间安排：" + Arrays.deepToString(intervals2));
        System.out.println("最多可以安排的会议数：" + maxMeetings(intervals2));

        // 测试用例3：完全不重叠
        int[][] intervals3 = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };
        System.out.println("\n测试3 - 完全不重叠：");
        System.out.println("会议时间安排：" + Arrays.deepToString(intervals3));
        System.out.println("最多可以安排的会议数：" + maxMeetings(intervals3));

        // 测试用例4：完全重叠
        int[][] intervals4 = { { 1, 10 }, { 2, 9 }, { 3, 8 }, { 4, 7 } };
        System.out.println("\n测试4 - 完全重叠：");
        System.out.println("会议时间安排：" + Arrays.deepToString(intervals4));
        System.out.println("最多可以安排的会议数：" + maxMeetings(intervals4));
    }

    /**
     * 跳跃游戏测试方法
     */
    public void testCanJump() {
        System.out.println("\n=== 跳跃游戏测试 ===");

        // 测试用例1：可以到达
        int[] nums1 = { 2, 3, 1, 1, 4 };
        System.out.println("测试1 - 可以到达：");
        System.out.println("跳跃数组：" + Arrays.toString(nums1));
        System.out.println("是否能到达最后一个位置：" + canJump(nums1));

        // 测试用例2：不能到达
        int[] nums2 = { 3, 2, 1, 0, 4 };
        System.out.println("\n测试2 - 不能到达：");
        System.out.println("跳跃数组：" + Arrays.toString(nums2));
        System.out.println("是否能到达最后一个位置：" + canJump(nums2));

        // 测试用例3：刚好到达
        int[] nums3 = { 1, 1, 1, 1 };
        System.out.println("\n测试3 - 刚好到达：");
        System.out.println("跳跃数组：" + Arrays.toString(nums3));
        System.out.println("是否能到达最后一个位置：" + canJump(nums3));

        // 测试用例4：单个元素
        int[] nums4 = { 0 };
        System.out.println("\n测试4 - 单个元素：");
        System.out.println("跳跃数组：" + Arrays.toString(nums4));
        System.out.println("是否能到达最后一个位置：" + canJump(nums4));
    }

    /**
     * 主测试方法
     */
    public static void main(String[] args) {
        CursorCreate solution = new CursorCreate();

        // 测试所有算法
        solution.testCombinationSum();
        solution.testPermute();
        solution.testMaxMeetings();
        solution.testCanJump();
    }
}